/*************************************************************************
    > File Name: transTB.cpp
    > Author: liujing
    > Mail: jingliu.cs@gmail.com 
    > Created Time: 2014年10月21日 星期二 21时15分28秒
 ************************************************************************/
#include "transTB.h"

State::State(void):isEnd(false){
	this->dfa_id=DFA_ID++;
}

State::~State(void){
}

int State::DFA_ID=0;

State::State(Graph* g, set<int> nfaIDs):isEnd(false){
	this->graph=g;
	//deep copy
	set<int>::iterator iter=nfaIDs.begin();
	for(;iter!=nfaIDs.end();iter++){
		(this->nfaStateIDs).insert(*iter);
	}
}

void State::resetDFAID(){
	DFA_ID=0;
}

int State::getDFAID(){
	return dfa_id;
}

bool State::isEqual(State* s){
	set<int> nfaIDs=s->nfaStateIDs;
	if(this->nfaStateIDs.size()!=s->nfaStateIDs.size()){
		return false;
	}
	set<int>::iterator tarIter=nfaIDs.begin();
	set<int>::iterator srcIter=this->nfaStateIDs.begin();
	while(true){
		if(tarIter==nfaIDs.end()){
			return true;
		}
		if(*tarIter!=*srcIter){
			return false;
		}
		tarIter++;
		srcIter++;
	}
}

bool State::isIntersect(State* s){
	set<int> nfaIDs=s->nfaStateIDs;
	set<int>::iterator tarIter=nfaIDs.begin();
	set<int>::iterator srcIter=this->nfaStateIDs.begin();
	for(;tarIter!=nfaIDs.end();tarIter++){
		if(this->nfaStateIDs.find(*tarIter)!=this->nfaStateIDs.end()){
			return true;
		}
	}
	return false;
}

//compute the ids of nodes which is reachable through str
State* State::move(wchar_t str){
	set<int> moveNfaIDs;
	int i,j=0;
	set<int>::iterator setIter=nfaStateIDs.begin();
	for(;setIter!=nfaStateIDs.end();setIter++){
		for(i=0;i<graph->graphLines.size();i++){
			if(*setIter==graph->graphLines[i]->graphNode->ID){
				for(j=0;j<graph->graphLines[i]->graphNodes.size();j++){
					if(graph->graphLines[i]->graphNodes[j]->str==str){
						moveNfaIDs.insert(graph->graphLines[i]->graphNodes[j]->graphNode->ID);
					}					
				}
			}
		}
	}
	return new State(this->graph,moveNfaIDs);
}

//get the e_colsure use the subset construction algorithm
//Note! eclosure should look recursively
/**State* State::eclosure(){
	int i,j=0;
	set<int>::iterator setIter=nfaStateIDs.begin();
	set<int> eSet;
	for(;setIter!=nfaStateIDs.end();setIter++){
		eSet.insert(*setIter);
		for(i=0;i<graph->graphLines.size();i++){
			if(*setIter==graph->graphLines[i]->graphNode->ID){
				for(j=0;j<graph->graphLines[i]->graphNodes.size();j++){
					if(graph->graphLines[i]->graphNodes[j]->str=='E'){
						eSet.insert(graph->graphLines[i]->graphNodes[j]->graphNode->ID);
					}
				}
			}
		}
	}
	return new State(this->graph,eSet);
}**/

State* State::eclosure(){
	set<int> eSet;
	set<int>::iterator setIter=nfaStateIDs.begin();
	vector<bool> visited(this->graph->graphLines.size(),false);
	for(;setIter!=nfaStateIDs.end();setIter++){
		eSet.insert(*setIter);
		dfs(this->graph,*setIter,&eSet,&visited);
	}
	return new State(this->graph,eSet);
}

/*deep first traversal for e_edge*/
void dfs(Graph* graph,int startNode,set<int>* eSet,vector<bool>* visited){
	//cout<<"dfs"<<startNode<<endl;
	if((*visited)[startNode]==true){
		return;
	}else{
		(*visited)[startNode]=true;
		eSet->insert(startNode);
		int j=0;
		for(j=0;j<graph->graphLines[startNode]->graphNodes.size();j++){
			if(graph->graphLines[startNode]->graphNodes[j]->str=='E'){
				dfs(graph,graph->graphLines[startNode]->graphNodes[j]->graphNode->ID,eSet,visited);
			}
		}
	}
}

void State::printState(){
	set<int>::iterator iter=this->nfaStateIDs.begin();
	for(;iter!=this->nfaStateIDs.end();iter++){
		cout<<*iter<< " ";
	}
	cout<<endl;
}

set<wchar_t> getAdjEdges(State* s){
	Graph * graph=s->graph;
	//test_print(graph);
	set<int>::iterator iterInt=(s->nfaStateIDs).begin();
	set<wchar_t> setChar;
	for(;iterInt!=(s->nfaStateIDs).end();iterInt++){
		int tempStateID=*iterInt;
		//cout<<tempStateID<<endl;
		int i,j,k=0;
		for(i=0;i<graph->graphLines.size();i++){
			if(graph->graphLines[i]->graphNode->ID==tempStateID){
				for(j=0;j<graph->graphLines[i]->graphNodes.size();j++){
					if(graph->graphLines[i]->graphNodes[j]->str!='E'){
						setChar.insert(graph->graphLines[i]->graphNodes[j]->str);
						//cout<<tempStateID<< "->"<<graph->graphLines[i]->graphNodes[j]->graphNode->ID;
						//cout<<char(graph->graphLines[i]->graphNodes[j]->str)<<endl;
					}
				}
			}
		}
	}
	return setChar;
}

TransTable::TransTable(void){
}

TransTable::~TransTable(void){
}

TransTable::TransTable(Graph* graph){
	this->stateSum=0;
	this->graph=graph;
}


void TransTable::buildTransitionTable(void){
	int startID=this->graph->start;
	int endID=this->graph->end;
	set<int> startKernel;
	startKernel.insert(startID);
	int dfaIndex=0;
	State *startState=new State(this->graph,startKernel);
	State *startEclosure=startState->eclosure();
	startEclosure->dfa_id=dfaIndex++;
	if((startEclosure->nfaStateIDs).find(this->graph->end)!=startEclosure->nfaStateIDs.end()){
		startEclosure->isEnd=true;
	}
	(this->states).push_back(startEclosure);		//this is the visit() operation
	//Breadth first traversal
	queue<State*> stateQueue;
	stateQueue.push(startEclosure);
	while(!stateQueue.empty()){
		State state=*stateQueue.front();
		State* p_state=stateQueue.front();
		//cout<<"state ID[top]: "<<state.dfa_id<<endl;
		stateQueue.pop();
		set<wchar_t> adjEdges=getAdjEdges(p_state);
		set<wchar_t>::iterator edgeIter=adjEdges.begin();
		for(;edgeIter!=adjEdges.end();edgeIter++){
			wchar_t trans_ch=*edgeIter;
			State *move_state=state.move(trans_ch);
			State *e_state=move_state->eclosure();
			int i=0;
			bool has_exist=false;
			for(i=0;i<this->states.size();i++){
				if(e_state->isEqual(this->states[i])){
					has_exist=true;
				}
			}
			if(!has_exist){
				e_state->dfa_id=dfaIndex++;
				if((e_state->nfaStateIDs).find(this->graph->end)!=e_state->nfaStateIDs.end()){
					e_state->isEnd=true;
				}
				p_state->nextStates.insert(pair<wchar_t,int>(trans_ch,e_state->dfa_id));
				stateQueue.push(e_state);
				(this->states).push_back(e_state);				
			}
		}
	}
	//after breadth first traversal, all states are recognized
	// to handle the circles
	handleCircles(this);
}

void handleCircles(TransTable* transtb){
	vector<State*> states=transtb->states;
	int i=0;
	for(i=0;i<states.size();i++){
		State* s=states[i];
		set<wchar_t> adjEdges=getAdjEdges(s);
		set<wchar_t>::iterator adjIter=adjEdges.begin();
		for(;adjIter!=adjEdges.end();adjIter++){
			State *move_state=s->move(*adjIter);
			int j=0;
			for(j=0;j<states.size();j++){
				//move_state->printState();
				//s->printState();
				if(move_state->isIntersect(states[j])){
					s->nextStates.insert(pair<wchar_t,int>(*adjIter,states[j]->dfa_id));
				}
			}
		}
	}
}



void TransTable::printTransTable(void){
	vector<State*> states=this->states;
	vector<State*>::iterator iter=states.begin();
	for(;iter!=states.end();iter++){
		State* s=*iter;
		set<int>::iterator nfaIDIter=s->nfaStateIDs.begin();
		cout<<"{";
		for(;nfaIDIter!=s->nfaStateIDs.end();nfaIDIter++){
			cout<<*nfaIDIter<<",";
		}
		cout<<"}  stateID:";
		cout<<s->dfa_id<<" ";
		//travel the map nextStates and print the infomation
		map<wchar_t,int>::iterator mapIter=s->nextStates.begin();
		for(;mapIter!=s->nextStates.end();mapIter++){
			cout<<mapIter->second<<"["<<char(mapIter->first)<<"],";
			
		}
		if(s->isEnd){
				cout<<" is End";
		}
		
		cout<<endl;
	}
	cout<<"start ID is: 0"<<endl;
}

